package zhoujian.oj.leetcode;

/**
 * @version 1.0
 * @description Given a sorted array, remove the duplicates in place such that
 *              each element appear only once and return the new length.
 * 
 *              Do not allocate extra space for another array, you must do this
 *              in place with constant memory.
 * 
 *              For example, Given input array A = [1,1,2], Your function should
 *              return length = 2, and A is now [1,2].
 * 
 */
public class RemoveDuplicatesFromSortedArray {

	public int removeDuplicates(int[] A) {
        if (null == A || A.length == 0)
            return 0;
        
        int pos = 0;
        for (int i = 1; i < A.length; ++i) {
            if (A[pos] != A[i]) {
                A[++pos] = A[i];
            }
        }
        
        return pos + 1;
    }

	public static void main(String[] args) {
		RemoveDuplicatesFromSortedArray removeDuplicates = new RemoveDuplicatesFromSortedArray();
		int[] A;

		A = new int[]{1, 1, 2};
		assert removeDuplicates.removeDuplicates(A) == 2;

		A = new int[]{1, 1, 2, 2, 2, 3, 3};
		assert removeDuplicates.removeDuplicates(A) == 3;

		A = new int[]{1, 2, 3, 4, 5};
		assert removeDuplicates.removeDuplicates(A) == 5;

		A = new int[]{1};
		assert removeDuplicates.removeDuplicates(A) == 1;

		A = new int[]{};
		assert removeDuplicates.removeDuplicates(A) == 0;

		assert removeDuplicates.removeDuplicates(null) == 0;
	}

}
